/****************************************************
          File Name:string.c
          Author: Abby Cin
          Mail: abbytsing@gmail.com
          Created Time: Fri 13 Feb 2015 10:27:05 AM CST
*****************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

static int ktime = 0;
static int ntime = 0;

int mymatcher2(char *T, char *P, int pos)
{
    int times = 0;
    register int n=0, m=0;
    int equal = 0;

    for(;T[n];) n++;
    for(;P[m];) m++;

    register int i, j;
    for(i=pos; i <= n-m; i++)   // must <= n-m
    {
        equal = 1;
        for(j=0; equal && j < m; j++)
            if(P[j] != T[i+j])
                equal = 0;
        if(equal) break;    // j == m
        j -= 1;     // restore j to before execute j++
        if(j != 0)
                i += j;  // when reached the end of parent loop, i will increase 1
        times++;
    }
    ktime += times;
    if(equal)
        return i;
    else
        return -1;
}


int mymatcher(char *T, char *P, int pos)
{
    int times = 0;
    register int n=0, m=0;
    int equal = 0;

    for(;T[n];) n++;
    for(;P[m];) m++;

    register int i, j;
    for(i=pos; i <= n-m; i++)   // must <= n-m
    {
        equal = 1;
        for(j=0; equal && j < m; j++)
            if(P[j] != T[i+j])
                equal = 0;
        if(equal) break;
        times++;
    }
    ntime += times;
    if(equal)
        return i;
    else
        return -1;
}
    

void Replace(char *S, char *T, char *V, int op)
{
    register int i,j, k, m;
    char *res;
    int len, lv, ls, lt, tmp = 0, re = 0; // must initailze tmp and re to 0
    lv = strlen(V);
    ls = strlen(S);
    lt = strlen(T);

    int pos[strlen(S) - strlen(T)];     // space get speed
    for(i=0;;i++, re++)
    {
        if(op == 1)
            re = mymatcher(S, T, re);
        else
            re = mymatcher2(S, T, re);
        pos[i]=re;
        if(tmp == pos[i] || re == -1) break; // found no more or not found
        tmp = pos[i];
    }
    
    len = ls + i*(lv - lt);

    i=0;
    if(pos[0] != -1)
    {
        res = (char *)malloc(len);
        for(m=0, j=0; j < len; j++, m++)
        {
            if(j == pos[i])
            {
                for(k=0; k<lv;k++,j++)
                    res[j] = V[k];
                i++;
                m += strlen(T);
                pos[i] += i*(lv -lt);   // re-calculate position
            }
            res[j]=S[m];
        }
        if(op == 1)
            printf("\e[36m暴力匹配:\t\e[0m%s\n", res);
        else
            printf("\e[31m我的改进:\t\e[0m%s\n", res);
        free(res);
    }
}

int main(int argc, char *argv[])
{
    char *T1,*T2;
    int res, reskmp;

    T1 = (char *)malloc(256);
    T2 = (char *)malloc(256);

    strcpy(T1, argv[1]);
    strcpy(T2, argv[1]);
    //res = mymatcher(T, P, 0);
    //reskmp = mymatcher2(T, P, 0);
    
    Replace(argv[1], argv[2], argv[3], 1);
    printf("暴力匹配 times: %d\n", ntime);
    Replace(argv[1], argv[2], argv[3], 2);
    printf("我的改进 times: %d\n", ktime);

    //printf("strstr: %s\n", strstr(argv[1], argv[2]));

    return 0;
}
